class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();

        if(n1==0 || n2==0) return n1+n2;

        vector<vector<int>> dp(n1+1, vector<int>(n2+1));

        for(int i = 0; i < n1+1; i++)
            dp[i][0] = i;
        for(int i = 0; i < n2+1; i++)
            dp[0][i] = i;

        for(int i = 1; i <= n1; i++)
        {
            for(int j = 1; j <= n2; j++)
            {
                int left = dp[i][j-1] + 1;
                int top = dp[i-1][j] + 1;
                int left_top = dp[i-1][j-1];
                if(word1[i-1] != word2[j-1]) left_top += 1;
                dp[i][j] = min(left, min(top, left_top));
            }
        }

        return dp[n1][n2];
    }
};